//设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存
//被填满时，它应该删除最近最少使用的项目。 
//
// 它应该支持以下操作： 获取数据 get 和 写入数据 put 。 
//
// 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value)
// - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。 
//
// 示例： 
//
// 
//LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
//
//cache.put(1, 1);
//cache.put(2, 2);
//cache.get(1);       // 返回  1
//cache.put(3, 3);    // 该操作会使得密钥 2 作废
//cache.get(2);       // 返回 -1 (未找到)
//cache.put(4, 4);    // 该操作会使得密钥 1 作废
//cache.get(1);       // 返回 -1 (未找到)
//cache.get(3);       // 返回  3
//cache.get(4);       // 返回  4
// 
//
// Related Topics 设计 哈希表 链表 双向链表 👍 205 👎 0


package LeetCode.editor.cn;


import javax.swing.plaf.PanelUI;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-09-11 14:23:39
 * @description 面试题 16.25.LRU 缓存
 
 */
 
public class LruCacheLcci {
    public static void main(String[] args) {
    //测试代码
    LruCacheLcci fun = new LruCacheLcci();

    
    }

//leetcode submit region begin(Prohibit modification and deletion)
/*
class LRUCache {
    */
/*
    * 1. 使用双向链表和哈希表实现
    * 2. 使用Java内置的LinkedHashMap
    *
    * *//*

    int size=0;
    LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();
    public LRUCache(int capacity) {
        size=capacity;
    }
    
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        int val=map.get(key);
        map.remove(key);
        map.put(key,val);
        return val;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            map.remove(key);
        }else{
            if(map.size()==size){
                map.remove(map.entrySet().iterator().next().getKey());
            }
        }
        map.put(key,value);
    }
}
*/
        //
//class LRUCache extends LinkedHashMap<Integer, Integer> {
//    private int capacity;
//
//    //loadfactor  负载因子当实际容量为额定容量的百分之时进行扩容，防止hash冲突，0.75可以较好的达到空间时间平衡
//    public LRUCache(int capacity) {
//        super(capacity, 0.75F, true);
//        this.capacity = capacity;
//    }
//
//    public int get(int key) {
//        return super.getOrDefault(key, -1);
//    }
//
//    public void put(int key, int value) {
//        super.put(key, value);
//    }
//
//    //linkedhashmap,默认的方法为空
//    @Override
//    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
//        return size() > capacity;
//    }
//}
   // 双向链表 + 哈希表

    class LRUCache{
        class Node{
            int key;
            int val;
            Node pre;
            Node ne;
            public Node(){}
            public Node(int key,int val){
                this.key=key;
                this.val=val;
            }
        }
        private int capacity;
        private Map<Integer,Node> map;
        private Node head,tail;
        private  int size;
        public LRUCache(int capacity) {
            this.capacity=capacity;
            map=new java.util.HashMap<>();
            head=new Node();
            tail=new Node();
            // 两个哑节点
            head.ne=tail;
            tail.pre=head;
            size=0;
        }
        public  int get(int k){
            if(!map.containsKey(k)){
                return -1;
            }
            Node node=map.get(k);
            // 移动到头部
            moveToHead(node);
            return node.val;
        }
        public int put(int k,int v){
            if(map.containsKey(k)){
                Node node=map.get(k);
                node.val=v;
                moveToHead(node);
            }else{
                Node node=new Node(k,v);
                map.put(k,node);
                addToHead(node);
                size++;
                if(size>capacity){
                    Node tail=removeTail();
                    map.remove(tail.key);
                    size--;
                }
            }
            return -1;
        }
        private void moveToHead(Node node){
            removeNode(node);
            addToHead(node);
        }
        private void removeNode(Node node){
            node.pre.ne=node.ne;
            node.ne.pre=node.pre;
        }
        private void addToHead(Node node){
            node.pre=head;
            node.ne=head.ne;
            head.ne.pre=node;
            head.ne=node;
        }
        private Node removeTail(){
            Node res=tail.pre;
            removeNode(res);
            return res;
        }
    }
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
